/*
842. 将数组拆分成斐波那契序列
已解答
中等
相关标签
相关企业
给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。

形式上，斐波那契式 序列是一个非负整数列表 f，且满足：

0 <= f[i] < 231 ，（也就是说，每个整数都符合 32 位 有符号整数类型）
f.length >= 3
对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]
另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
*/

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> splitIntoFibonacci(string num) {
        vector<int> result;
        backtrack(result, num, 0, 0, 0);  // 从第一个字符开始递归
        return result;
    }

    bool backtrack(vector<int>& result, const string& num, int index, long long sum, int prev) {
        // 如果遍历完整个字符串，且结果数组有至少3个元素，返回成功
        if (index == num.size()) {
            return result.size() >= 3;
        }

        long long curr = 0;
        // 从当前索引开始，尝试所有可能的切分
        for (int i = index; i < num.size(); i++) {
            // 如果当前数字以 '0' 开头且长度大于1，直接跳过
            if (i > index && num[index] == '0') {
                break;
            }

            // 更新当前数字
            curr = curr * 10 + num[i] - '0';

            // 如果当前数字大于 INT_MAX，提前剪枝
            if (curr > INT_MAX) {
                break;
            }

            // 如果当前结果数组中至少有两个数，检查斐波那契条件
            if (result.size() >= 2) {
                if (curr < sum) {
                    continue;  // 当前数字小于斐波那契和，继续尝试下一个数字
                } else if (curr > sum) {
                    break;  // 当前数字大于斐波那契和，不再继续
                }
            }

            // 加入当前数字到结果数组
            result.push_back(curr);

            // 继续递归，检查下一个位置
            if (backtrack(result, num, i + 1, prev + curr, curr)) {
                return true;
            }

            // 回溯，移除当前数字
            result.pop_back();
        }

        return false;  // 没有找到有效的斐波那契数列
    }
};